package everyday;

/**
 * @author zhangmin
 * @create 2022-05-03 10:04
 * 比特位计数
 * 给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
 *
 * 思路：
 * dp[i]表示i中1的比特位数量，dp[i]=dp[i&(i-1)]+1。i&(i-1)会将i的最低位1变成0
 */
public class countBits338 {
    public int[] countBits(int n) {
        int[] dp=new int[n+1];
        for (int i = 1; i <= n; i++) {
            dp[i]=dp[i&(i-1)]+1;
        }
        return dp;
    }
}
